package com.janlei.tree;

import java.util.Stack;

/**
 * binary tree
 */
public class Tree {
    Node root;
    Integer height;

    public Tree(Node root, Integer height) {
        this.root = root;
        this.height = height;
    }

    public static void sortByHead(Node node) {
        if (node == null)
            return;

        System.out.println(node.data);
        sortByHead(node.left);
        sortByHead(node.right);
    }

    public static void sortByMid(Node node) {
        if (node == null)
            return;

        sortByMid(node.left);
        System.out.println(node.data);
        sortByMid(node.right);
    }

    public static void sortByTail(Node node) {
        if (node == null)
            return;

        sortByTail(node.left);
        sortByTail(node.right);
        System.out.println(node.data);
    }

    public static void sortByStack(Node node) {
        Stack<Node> stack = new Stack<>();

        //未结束
        while (node != null || !stack.isEmpty()) {

            //入栈
            while (node != null) {
                //前序遍历
                System.out.println(node.data);
                stack.push(node);
                node = node.left;
            }

            //出栈
            if (!stack.isEmpty()) {
                node = stack.pop();
                node = node.right;
            }
        }
    }
}

class Node {

    Node left;

    Node right;

    Integer data;

    public Node(Node left, Node right, Integer data) {
        this.left = left;
        this.right = right;
        this.data = data;
    }
}